{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Beautiful Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #divide-and-conquer #ordered-set #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #分治 #有序集合 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulPair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美数对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个长度相同的 <strong>下标从 0 开始</strong> 的整数数组 <code>nums1</code> 和 <code>nums2</code>&nbsp;，如果 <code>|nums1[i] - nums1[j]| + |nums2[i] - nums2[j]|</code> 在所有可能的下标对中是最小的，其中 <code>i &lt; j</code> ，则称下标对 <code>(i,j)</code> 为 <strong>美</strong> 数对，</p>\n",
    "\n",
    "<p>返回美数对。如果有多个美数对，则返回字典序最小的美数对。</p>\n",
    "\n",
    "<p>注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>|x|</code> 表示 <code>x</code> 的绝对值。</li>\n",
    "\t<li>一对索引 <code>(i1, j1)</code> 在字典序意义下小于 <code>(i2, j2)</code> ，当且仅当 <code>i1 &lt; i2</code> 或 <code>i1 == i2</code> 且 <code>j1 &lt; j2</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,2,3,2,4], nums2 = [2,3,1,2,3]\n",
    "<b>输出：</b>[0,3]\n",
    "<b>解释：</b>取下标为 0 和下标为 3 的数对，计算出 |nums1[0]-nums1[3]| + |nums2[0]-nums2[3]| 的值为 1 ，这是我们能够得到的最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,2,4,3,2,5], nums2 = [1,4,2,3,5,1]\n",
    "<b>输出：</b>[1,4]\n",
    "<b>解释：</b>取下标为 1 和下标为 4 的数对，计算出 |nums1[1]-nums1[4]| + |nums2[1]-nums2[4]| 的值为 1，这是我们可以达到的最小值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums1.length == nums2.length</code></li>\n",
    "\t<li><code>0 &lt;= nums1<sub>i</sub><sub>&nbsp;</sub>&lt;= nums1.length</code></li>\n",
    "\t<li><code>0 &lt;= nums2<sub>i</sub>&nbsp;&lt;= nums2.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [beautiful-pairs](https://leetcode.cn/problems/beautiful-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [beautiful-pairs](https://leetcode.cn/problems/beautiful-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2,4]\\n[2,3,1,2,3]', '[1,2,4,3,2,5]\\n[1,4,2,3,5,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        ans = [n, n]\n",
    "        h = {}\n",
    "        a = []\n",
    "        # 查找相同的对\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if (x, y) in h:\n",
    "                i0, i1 = min(h[(x, y)], i), max(h[(x, y)], i)\n",
    "                if i0 < ans[0] or (i0 == ans[0] and i1 < ans[1]):\n",
    "                    ans[0] = i0\n",
    "                    ans[1] = i1\n",
    "            else:\n",
    "                h[(x, y)] = i\n",
    "            a.append((x, y, i))\n",
    "        \n",
    "        if ans[0] < n and ans[1] < n:\n",
    "            return ans\n",
    "        \n",
    "        # 排序并使用有序集合查找\n",
    "        a.sort()\n",
    "        mn = n * 3\n",
    "        s = SortedList(key=lambda x: x[1])\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            while l < i and a[i][0] - a[l][0] > mn:\n",
    "                s.remove(a[l])\n",
    "                l += 1\n",
    "            idx = s.bisect_left((a[i][0], a[i][1] - mn, -1))\n",
    "            while idx < len(s) and s[idx][1] - a[i][1] <= mn:\n",
    "                d = abs(s[idx][0] - a[i][0]) + abs(s[idx][1] - a[i][1])\n",
    "                i0, i1 = min(s[idx][2], a[i][2]), max(s[idx][2], a[i][2])\n",
    "                if d < mn or (d == mn and i0 < ans[0]) or (d == mn and i0 == ans[0] and i1 < ans[1]):\n",
    "                    mn = d\n",
    "                    ans[0] = i0\n",
    "                    ans[1] = i1\n",
    "                idx += 1\n",
    "            s.add(a[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        ans = [n, n]\n",
    "        h = {}\n",
    "        a = []\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if (x, y) in h:\n",
    "                i0, i1 = min(h[(x, y)], i), max(h[(x, y)], i)\n",
    "                if i0 < ans[0] or i0 == ans[0] and i1 < ans[1]:\n",
    "                    ans[0] = i0\n",
    "                    ans[1] = i1\n",
    "            else:\n",
    "                h[(x, y)] = i\n",
    "            a.append((x, y, i))\n",
    "        \n",
    "        if ans[0] < n and ans[1] < n:\n",
    "            return ans\n",
    "        \n",
    "        a.sort()\n",
    "        mn = n * 3\n",
    "        s = SortedList(key=lambda x: x[1])\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            while l < i and a[i][0] - a[l][0] > mn:\n",
    "                s.remove(a[l])\n",
    "                l += 1\n",
    "            idx = s.bisect_left((a[i][0], a[i][1] - mn, -1))\n",
    "            while idx < len(s) and s[idx][1] - a[i][1] <= mn:\n",
    "                d = abs(s[idx][0] - a[i][0]) + abs(s[idx][1] - a[i][1])\n",
    "                i0, i1 = min(s[idx][2], a[i][2]), max(s[idx][2], a[i][2])\n",
    "                if d < mn or d == mn and i0 < ans[0] or d == mn and i0 == ans[0] and i1 < ans[1]:\n",
    "                    mn = d\n",
    "                    ans[0] = i0\n",
    "                    ans[1] = i1\n",
    "                idx += 1\n",
    "            s.add(a[i])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
